Pored $NZD(a,b)$ vraća i vrednosti $x$ i $y$ takve da je $NZD(a,b)=x\cdot a + y\cdot b$
def ext_gcd(a, b):
if b == 0:
return (a, 1, 0)
g, x, y = ext_gcd(b, a % b)
return (g, y, x - a // b * y)
a = 36
b = 81
(g, x, y) = ext_gcd(a, b)
print(f'NZD({a},{b}) = {g}')
print(f'{g} = ({x})*{a} + ({y})*{b}')